#leetcode题目18：四数之和
#难度：中等
#时间复杂度：O(n^3)
#空间复杂度：O(1)
#方法：双指针
#视频没有认真讲
from typing import List
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        if len(nums)<4:
            return []
        nums.sort()
        ans=set()
        for i in range(len(nums)-3):
            for j in range(i+1,len(nums)-2):
                now=nums[i]+nums[j] #使用两数之和的思想
                p=j+1
                q=len(nums)-1
                while p<q:
                    if nums[p]+nums[q]+now==target:
                        if (nums[i],nums[j],nums[p],nums[q]) not in ans:
                            ans.add((nums[i],nums[j],nums[p],nums[q]))
                        p+=1
                        q-=1

                    elif nums[p]+nums[q]+now>target:
                        q-=1
                    else:
                        p+=1
        return list(ans)



#测试数据
nums=[1,0,-1,0,-2,2]
target=0
#预期输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
solution=Solution()
print(solution.fourSum(nums,target))


